package acwing.算法进阶打卡;

/**
 * @author： li
 * @date： 2022-03-13 10:15
 * @version 1.0
 */
import java.util.*;
public class 最短Hamilton路径 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N=20,M=1<<N;
        int[][] f=new int[M][N];
        int[][] w = new int[N][N];//w表示的是无权图
        int n = sc.nextInt();
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++){
                w[i][j] = sc.nextInt();
            }
        for(int i=0;i<(1<<N);i++)
            Arrays.fill(f[i], (int) 1e9);//因为要求最小值，所以初始化为无穷大
//        System.out.println(Arrays.toString(f[1]));
        f[1][0]=0;//因为零是起点,所以f[1][0]=0;
        for(int i=0;i<1<<n;i++)//i表示所有的情况
            for(int j=0;j<n;j++)//j表示走到哪一个点
                if(((i>>j)&1)==1)
                    for(int k=0;k<n;k++)//k表示走到j这个点之前,以k为终点的最短距离
                        if(((i>>k)&1)==1)
                            f[i][j]=Math.min(f[i][j],f[i-(1<<j)][k]+w[k][j]);//更新最短距离
        System.out.println(f[(1<<n)-1][n-1]);//表示所有点都走过了,且终点是n-1的最短距离
        //位运算的优先级低于'+'-'所以有必要的情况下要打括号
    }
}
